 // DFSTraversal.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

struct TreeNode
{
    int value;
    TreeNode *left, *right;
};

// Pre-Order, recursive
void PreOrder_Recurtive(TreeNode *root)
{
    if(!root) return;
    cout<<root->value<<endl;
    PreOrder_Recurtive(root->left);
    PreOrder_Recurtive(root->right);
}

// Pre-Order, iterative 1
void PreOrder_Iterative1(TreeNode *root)
{
    if(!root) return;
    stack<TreeNode *> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode *p=s.top();
        s.pop(); // must
        cout<<p->value<<endl;
        if(p->right) s.push(p->right);
        if(p->left) s.push(p->left);
    }
}

// Pre-Order, iterative 2
void PreOrder_Iterative2(TreeNode *root)
{
    if(!root) return;

    stack<TreeNode *> s;
    s.push(root);
    int last=0; // 0: from up, 1: from left, 2: from right. Representing where it's returned (from the last visited node)

    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            cout<<p->value<<endl;

            if(p->left)
            {
                last=0; // up
                s.push(p->left);
            }
            else
            {
                last=1; // left
            }
        }
        else if(last==1)
        {
            if(p->right)
            {
                last=0; // up
                s.push(p->right);
            }
            else
            {
                last=2; // right
            }
        }
        else if(last==2)
        {
            s.pop();
            if(!s.empty()&&s.top()->left==p)
            {
                last=1; // left
            }
            else
            {
                last=2; // right
            }
        }
        else
            throw; // error
    }
}

// In-Order, recursive
void InOrder_Recursive(TreeNode *root)
{
    if(!root) return;
    InOrder_Recursive(root->left);
    cout<<root->value<<endl;
    InOrder_Recursive(root->right);
}

// In-Order, iterative
void InOrder_Iterative(TreeNode *root)
{
    if(!root) return;

    stack<TreeNode *> s;
    s.push(root);
    int last=0; // 0: from up, 1: from left, 2: from right

    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            if(p->left)
            {
                last=0; // up
                s.push(p->left);
            }
            else
            {
                last=1; // left
            }
        }
        else if(last==1)
        {
            cout<<p->value<<endl;

            if(p->right)
            {
                last=0; // up
                s.push(p->right);
            }
            else
            {
                last=2; // right
            }
        }
        else if(last==2)
        {
            s.pop();
            if(!s.empty()&&s.top()->left==p)
            {
                last=1; // left
            }
            else
            {
                last=2; // right
            }
        }
        else
            throw; // error
    }
}


// Post-Order, recursive
void PostOrder_Recursive(TreeNode *root)
{
    if(!root) return;
    PostOrder_Recursive(root->left);
    PostOrder_Recursive(root->right);
    cout<<root->value<<endl;
}

// Post-Order, iterative
void PostOrder_Iterative(TreeNode *root)
{
    if(!root) return;

    stack<TreeNode *> s;
    s.push(root);
    int last=0; // 0: from up, 1: from left, 2: from right

    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            if(p->left)
            {
                last=0; // up
                s.push(p->left);
            }
            else
            {
                last=1; // left
            }
        }
        else if(last==1)
        {
            if(p->right)
            {
                last=0; // up
                s.push(p->right);
            }
            else
            {
                last=2; // right
            }
        }
        else if(last==2)
        {
            cout<<p->value<<endl;

            s.pop();
            if(!s.empty()&&s.top()->left==p)
            {
                last=1; // left
            }
            else
            {
                last=2; // right
            }
        }
        else
            throw; // error
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    return getchar();
}